package q187_findRepeatedDnaSequences;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        Solution s1 = new Solution();
        s1.findRepeatedDnaSequences(s);
    }

    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            // 必须是等于2 否则某序列出现三次 则会被重复添加
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;

    }
}
